Exercici 9 (Tasca 7).
(NP,
coNP,
DP,
Unique SAT)
\mathtt{Unique SAT}
La classe \mathsf{DP} (de difference polynomial time) es defineix com el conjunt de llenguatges L per als quals existeixen dos llenguatges L_1 \in \mathsf{NP}, L_2 \in \mathsf{coNP} tals que L = L_1 \cap L_2. Cal notar que, com que \overline{L_2} \in \mathsf{NP}, L és la diferència de dos conjunts de \mathsf{NP} (però no confongueu \mathsf{DP} amb \mathsf{NP} \cap \mathsf{coNP}, que s’assembla superficialment).
Considereu el problema \mathtt{Unique SAT}, que consisteix a determinar si una fórmula booleana té una única assignació satisfactible (o model) i demostreu els següents fets.
- \mathtt{Unique SAT} \in \mathsf{DP}.
- Si \mathtt{Unique SAT} és a \mathsf{NP}, aleshores \mathsf{NP} = \mathsf{coNP}.